The present invention relates to a method to share available bandwidth, a processor realizing such a method and a scheduler, an intelligent buffer and a telecommunication system.
Such a method to share available bandwidth is already known in the art, e.g. from the article xe2x80x9cA flexible buffer acceptance algorithm to support a guaranteed frame rate service category in asynchronous transfer mode ATM switchesxe2x80x9d written by O. Bonaventure and presented at IFIP ATM 98 workshop, Jul. 20-22, 1998 pages 77/7 to 71/10. Therein, a flexible buffer acceptance algorithm to support the Guaranteed Frame Rate GFR service category in Asynchronous Transfer Mode switches is described. The GFR service is one of the service categories which are specified for different kind of network applications. For each kind of service, a set of parameters is given in order to describe the traffic presented to the network and the Quality of Service which is required of the network. In order to meet the desired QOS objectives different kind of traffic control mechanisms are defined.
A method to share available bandwidth on a common link in a communication network among a plurality of data flows which are transmitted via the common link is described in this article, in particular, for the guaranteed frame rate GFR service. It is described in this article that the objective of the Guaranteed Frame Rate GFR service category is to provide a service with a minimum guaranteed bandwidth which is easy to use for the end-systems. While no modifications are strictly required to the end-systems to benefit from the guaranteed frame rate GFR service category, particular functional blocks such as switches or routers must be enhanced to support this service category.
Indeed, in section 2 of the above mentioned paper it is mentioned that the main motivation behind the introduction of the GFR service category was to keep the simplicity of the Unspecified Bit Rate service category UBR while providing a better service by allowing a minimum guaranteed bandwidth to be associated with each virtual connection, called in this application data flow, which make use of such a common link. A traffic contract for such a GFR service includes the definition of a Minimum Cell Rate MCR for each data flow. Such a minimum cell rate MCR corresponds to a minimum guaranteed bandwidth, expressed e.g. in cells per second. The minimum guaranteed bandwidth is the minimum bandwidth which is guaranteed at any time for each established data flow following its contract and is determined during connection set-up of the data flow. This means that the guaranteed bandwidth is available on the common link for each established data flow and that it is used or not used for this established data flow.
In this way, a method to share available bandwidth on a common link includes a step of sharing reserved bandwidth included in the available bandwidth among the plurality of data flows. A possible way to share the available bandwidth, as it is described in the article for the GFR service, is in function of its minimum cell rate MCR.
It has to be remarked that, as it is also mentioned in the article, the available bandwidth which is shared among the data flows in proportion to their MCR is not necessarily a constant bandwidth. Indeed, in addition to the GFR service category, an e.g. ATM switch might be able to support other service categories. In such a multi-service switch, the available bandwidth to the GFR service data packet streams is not constant anymore but depends on the amount of higher priority traffic e.g. real-time traffic. This means that the total bandwidth over the common link might be bigger and distributed to other kinds of services like real time services whereof in time delivery of the packets is important. It has to be understood that connection admission control algorithms ensure that a predefined average bandwidth is always available to the GFR data flows above the sum of the different minimum cell rates of all GFR data flows.
It is also mentioned in the article that the GFR service also provides the advantage to the end-system to transmit data packets, which are included in such a data flow, in excess of the minimum cell rate MCR being associated to its data flow. A method to share available bandwidth which is mentioned in the article of paragraph 7.1, i.e. the Double EPD mechanism, has however the drawback that the allocation of the excess bandwidth, called unreserved bandwidth can not be controlled at all. On the other hand, paragraph 7.3 of the article mentions two algorithms which are controlling this unreserved bandwidth: one implementation provides a fair allocation of the unreserved bandwidth and another implementation distributes the unreserved bandwidth in proportion to the MCR of the data flows. In this way, a method to share available bandwidth on a common link includes a step of sharing unreserved bandwidth, which is in excess of the reserved bandwidth, according to a respective unreserved data packet share which is associated to each one of the data flows.
A drawback of these prior art algorithms is that they are however sharing the unreserved bandwidth following a particular strategy e.g. fair share for all data flows or a share in function of their minimum cell rate MCR. This means that the unreserved data packet share is predefined by the known algorithms. There is no flexibility for the network operators to define their own policies for sharing the excess bandwidth.
An object of the present invention is to provide a method to share available bandwidth such as the above known types but which provides to the network operator the flexibility to define their own policies for sharing the unreserved bandwidth.
According to the invention, this object is achieved by the method to share available bandwidth, and a processor realizing the method, and a scheduler, a intelligent buffer and a telecommunication system including such a processor.
Indeed, due to the fact that the step of sharing the unreserved bandwidth includes associating to one of the data flows a respective adaptable administrative weight and the step of determining the respective unreserved data packet share of this data flow in function of its respective adaptable administrative weight, the network operator has the ability, in addition to the sharing of the reserved bandwidth, to provide administrative weights for each data flow. These administrative weights are reflecting the operator""s policy to share the unreserved bandwidth.
The flexibility of the proposed method of the invention allows the network operator not only to support the policies of the prior art solutions, i.e. providing a fair allocation or distribution of the unreserved bandwidth following the minimum cell rates of the data flows, but also to define its own policy e.g. an operator can favor its own local network traffic over transit traffic coming from another network.
It has to be explained that different kinds of implementations are possible in order to translate a share of the unreserved bandwidth. Indeed, the adaptable administrative weight can be implemented by a xe2x80x9cweightxe2x80x9d of the unreserved bandwidth, i.e. a percentage of the unreserved bandwidth e.g. adaptable administrative weight equal to 30%; but another implementation can be translated by a xe2x80x9cratexe2x80x9d e.g. data packet rates in proportion to each other. This will become more clear in the following paragraph.
The adaptable administrative weights can be used by the network operator in order to give a different fraction of the unreserved bandwidth to the different data flows.
A first example is given in the event when the network operator wants that all the data flows receive a same fraction of the unreserved bandwidth, then the operator enters for all the data flows a same adaptable administrative weight e.g. 1.
A second example is given in the event when the network operator wants to distribute the unreserved bandwidth in proportion to the minimum guaranteed bandwidth, the adaptable administrative weights of the different data flows should be set to e.g. its minimum data packet rate.
A third example is given in the event when the network operator wants to support two types of data flows e.g. gold data flows and normal data flows. Presume that the gold data flows are receiving a ten times larger fraction of the unreserved bandwidth than the normal data flows. This can be implemented in two different ways:
each adaptable administrative weight of a gold data flow is a value which is ten times larger than the value of each administrative weight of a normal data flow. In this way, each gold data flow receives a share of the unreserved bandwidth that is ten times larger than the share of the unreserved bandwidth for a normal data flow. This implementation is independent of the number of data flows included in the gold class of data flows and independent of the number of data flows included in the normal class of data flows; and
the global share of the unreserved bandwidth for all the gold data flows together is ten times larger as the global share of the unreserved bandwidth for all the normal data flows together, whereby this global gold share is equally divided among the number of gold data flows and the global normal share is equally divided among the number of normal data flows. The adaptable administrative weights are implemented accordingly. This implementation is dependent of the number of data flows included in the gold class of data flows and of the number of data flows included in the normal class of data flows.
It has to be remarked that, an advantage of the method of the invention becomes clear with the following possible implementation of the adaptable administrative weight. Indeed, when the adaptable administrative weight is made dependent of other parameters such as e.g. time, the network operator implements its policy in advance whereby later on the administrative weights are changing i.e. are adapted, in function of such a parameter, without any actual intervention of the operator. This will become more clear with the following example. In the event when the operator wants to give to all the data flows a same fraction of the unreserved bandwidth during peak periods of the day and when the operator wants to support two classes of data flows, as described above with gold data flows and normal data flows, during the rest of the day, the data flows are receiving an adaptable administrative weight which are a function of a time-counter. In this way, the operator implements its policy in advance whereby e.g. during a predefined time moment of a day the values of the adaptable administrative weights are adapted, without any actual intervention of the operator, whereby the administrative weights of the different data flows are all receiving a same value. Later on at a second predetermined time, the administrative weights are again adapted, without any actual intervention of the operator, whereby the administrative weights of the different data flows are receiving a value according to the gold data flow or a value according to the normal data flow. Even more, the adaptable administrative weight might depend on more than one variable. Indeed, according the above example, beside the time counter a variable might be entered for each class of data flow e.g. WG for the gold class of data flows or WN for the normal class of data flows, whereby a relative value of a data packet rate is given to WG and to WN. In the event when e.g. the gold class of data flow would receive three times more bandwidth than the normal class of data flows the WG variable is put to 1 and the WN variable is put to 1/3. However, in the event when the operator wants to the change the bandwidth share for each class of data flows, only the value of the variables WG and WN needs to be adapted e.g. WG is put to 1 and WN is put to 1/4.
A more efficient use of the available bandwidth is to distribute the unreserved bandwidth towards active data flows i.e., data flows whereof at least one data packet is included in the buffer means which is coupled to the processor of the invention. Indeed, a possible way to share the unreserved bandwidth according to the method of the invention is to distribute a share of the unreserved bandwidth to all the established data flows. However, the share for a data flow that is transmitting e.g., data packets in bursts and whereof no data packet is currently present in the buffer could better be used by other data flows.
It has to be remarked that the method of the invention efficiently supports the coexistence of data flows with and without a minimum bandwidth guarantee, which is an advantage in order to support different kinds of service categories. Therein it is described that the processor according to the present invention further includes first determining means to determine the respective reserved data packet share in function of a minimum data packet rate which is associated to each data flow and which guarantees for each data flow a minimum guaranteed bandwidth, and that the control means is further included in the processor to activate the second processing means in the event when the minimum guaranteed bandwidth is respected due to the first processing means. In this way the unreserved bandwidth is only shared if all data flows, or according to the above described implementation if all active data flows, are already receiving their minimum guaranteed bandwidth with the step of sharing the reserved bandwidth.
Different kinds of service categories which are supporting a minimum bandwidth guarantee are known, however an important application of the present invention is that the processor of the invention supports the guaranteed frame rate service category in an asynchronous transfer mode telecommunication system. It has to be remarked that, in the event when the method of the invention is used to support the guaranteed frame rate service category, the method de-couples the sharing process of the unreserved bandwidth from the provisioning of the minimum bandwidth guarantees.
An advantage of the method according to the invention is that in order to support best effort data flows together with data flows with a minimum guaranteed bandwidth, according to prior art implementations, a minimum bandwidth is usually implicitly defined and reserved for each data flow. This is however not necessary when the available bandwidth is shared according to the method of the invention. Indeed, data flows which have a predefined minimum data packet share which is equal to zero are allowed to have an adaptable administrative weight which is different from zero and are getting a share of the unreserved bandwidth according to an unreserved data packet share being a function of its adaptable administrative weight when e.g. the data flow becomes active.
Yet, it has to be remarked that the processor of the invention can be implemented as mentioned above with fixed-length data packets, e.g., ATM cells but that it is also possible to extend the implementation of the processor according to the invention to support as well variable length packets, e.g., Internet Packets. In this way, the processor of the invention supports, e.g., a controlled load service in an Internet Protocol Telecommunication system.
In another implementation according to the present invention, the processor further controls a buffer means that stores received data packets. Furthermore the step of sharing reserved bandwidth is constituted by a first process of sharing guaranteed bandwidth up to an amount of reserved bandwidth. The reserved bandwidth is predefined for each data flow and is included in the available bandwidth. The step of sharing unreserved bandwidth is constituted by a second process of sharing non-guaranteed bandwidth among the plurality of data flows according to a respective non-guaranteed bandwidth share. The non-guaranteed bandwidth comprises the unreserved bandwidth as well as the actually unused part of the reserved bandwidth. The unreserved bandwidth is included in the available bandwidth in excess of the reserved bandwidth. The second process of sharing the non-guaranteed bandwidth includes associating the respective adaptable administrative weight to at least one of the data flows. The respective non-guaranteed bandwidth share is herewith determined as a function of the respective adaptable administrative weight associated to the data flow.
A drawback of an implementation with two processors is that the first processor works with a non-work conserving principle that updates relevant scheduling parameters as a function of a real time clock, while the second processor works with a work conserving principle that updates relevant scheduling parameters as a function of a virtual time clock. Hereby, two distinct schedulers are required to handle the respective scheduling parameters: a first scheduler to handle the scheduling parameters versus the real time clock and a second scheduler to handle the scheduling parameters versus the virtual time clock.
A further implementation of the present invention that avoids the above drawback. Indeed, such a method further includes performing at each service time moment the steps of:
determining, by means of a mode determining means included in the control means, whether for at least each active data flow of the plurality of data flows, a respective entitled reserved bandwidth share of said reserved bandwidth has been reached or not; and
selecting, when at least one active data flow has not reached its respective entitled reserved bandwidth share, one of the plurality of active data flows not having reached its entitled reserved bandwidth share, whereby guaranteed bandwidth is granted at the service time moment, and
selecting, when each one of the plurality of active data flows has reached its respective entitled reserved bandwidth share, one of the plurality of active data flows, whereby non-guaranteed bandwidth is granted at that service time moment.
Accordingly, this implementation makes use of a mode determining means which readily indicates, at each service time moment, under which mode G or NG bandwidth should be granted to a data flow, i.e. whether, at that service time moment, guaranteed bandwidth is to be granted in mode G or non-guaranteed bandwidth is to be granted in mode NG.
A first advantage of such an implementation is that, due to the foregoing decision made by the mode determining means, only one scheduler is really necessary to execute the subsequent data flow selection process for granting guaranteed or non-guaranteed bandwidth. Indeed, the common scheduler selects for at service time moment, according to its mode G or NG, either a data flow out of the plurality of active data flows that have not yet reached their entitled reserved bandwidth share, in mode G, or just one of the plurality of active data flows, in mode NG.
In this way for each data flow it is determined, whether or not it has been so far granted with its entitled number of cell service time occurrences which means that its guaranteed bandwidth granted condition is reached, i.e. when its respective entitled reserved bandwidth share is reached. Herewith the scheduler operates either in mode G, when at least one active data flow has not reached its guaranteed bandwidth granted condition, or the scheduler works in mode NG when either all data flows have reached thier guaranteed bandwidth granted condition or when all the data flows that have not reached their guaranteed bandwidth granted condition are inactive.
A second advantage of such an implementation is that, when sharing guaranteed bandwidth in mode G, the operation of the scheduler is here work conserving, since Mode G is always performed in priority over Mode NG.
According to such an implementation, a further characteristic feature is described such that the method further includes the steps of:
associating to each one of the plurality of data flows a respective service grant counter and;
initializing the service grant counter at each start of a predefined time period to a respective predefined initial credit value that is derived from the reserved bandwidth as being equal to the corresponding number of entitled service grants for reserved bandwidth during the predefined time period; and
updating, at each service time moment, the respective service grant counter that is associated to the data flow being served at the service time moment, until a respective predefined end value is reached for the respective service grant counter; and
detecting that an entitled respective reserved bandwidth share of a data flow is reached when the associated service grant counter reached the respective predefined end value.
This principle comprises the control of the scheduling operation for each data flow, over a predetermined time period, by means of a per data flow service grant counter for each session that is initialized with a credit value that reflects the corresponding number of entitled service grants for reserved bandwidth for that data flow over the new time period. Thus, by monitoring the current content of the respective service grant counters of all data flows, the scheduler to work, at each service time moment, either in mode G or in mode NG.
It has to be remarked here that the present invention is not limited to implementations such as described above i.e. initializing the respective service grant counters at the beginning of a predefined time period with a predetermined amount of credits and updating the respective service grant counters each time when the associated data flow is served. Indeed, an alternative implementation of the present invention is realized in the event when the respective service grant counters are provisioned on a continuous base proportional to the corresponding number of entitled service grants for reserved bandwidth for its data flow. Such an implementation provides a better performance and avoids a periodic initialization at the beginning of a predefined time period.
A further characteristic feature is described that, when successively serving complete packets of variable length, the step of updating the respective service grant counter is performed by counting a number of service grants in proportion to the length of the served packet. Indeed, in this way the scheduler allows to handle as well fixed length data packets as variable length data packets, i.e., complete frames.
A further remark is that different organization approaches are possible for initializing the service grant counters.
A first solution is described that the predefined time period has the same duration for all data flows.
A further solution is described in that the predefined time period of the same duration is synchronized for all data flows. In this way, the step of initializing the service grant counter of each data flow at each start of the predefined time period is performed simultaneously for all service grant counters of all data flows.
Another alternative solution is described in that the predefined time period of same duration is not synchronized for all data flows. The step of initializing the service grant counter of each data flow at each start of the predefined time period is not performed simultaneously for all service grant counters of all data flows.
Another implementation of the time intervals is described whereby the predefined time period has a specific duration, possibly different, for each data flow. Indeed, in such an alternative solution, the data flow scheduling time intervals have a different duration for each data flow and their time intervals are mutually phased asynchronously. The scheduler operation is no longer correlated at all for all data flows as in the first solution or, to a lesser extent, as in the previous solution.
A further characteristic feature to implement the present invention comprises determining whether a respective entitled reserved bandwidth share of the reserved bandwidth has been reached or not for at least each active data flow, includes a mode determining means using a common guaranteed bandwidth share data flow counter. The common guaranteed bandwidth share data flow counter records the current number of active data flows which have not reached so far their respective entitled reserved bandwidth share of the reserved bandwidth.
Furthermore, it is to be explained that, in order to implement the present invention, different types of scheduling arrangements are possible. These scheduling arrangements are described and are explained in further paragraphs.
An output signal of the processor i.e. a shared bandwidth signal which is a measure for the respective reserved data packet share and the respective unreserved data packet share is provided at an output of processor. It has to be remarked that this shared bandwidth signal can be implemented in different ways.
A possible way to reflect the result of the shared reserved bandwidth and the shared unreserved bandwidth is to generate a sequence of identifications of the data flows which are allowed to transmit its following data packet on the common link. This can be realized with a scheduler included in a communication network in order to share available bandwidth on a common link among a plurality of data flows. The scheduler includes a buffer means in order to sort the incoming data packets according to the data flow whereto the data packets belong into a plurality of buffer queues. Each buffer queue included in the buffer means is associated to a data flow. In this way a plurality of sorted data packets in the different buffer queues is provided. The scheduler includes also selection means in order to select one of the sorted data packets and in order to transmit the selected data packet on the common link. The scheduler further includes the processor according to the invention that is coupled to the selection means. The shared bandwidth signal of the processor is provided to the selection means in order to control the selection of the sorted data packets of the different queues.
It has to be remarked that the sorting function of the buffer means can be implemented in different ways i.e. physical queuing or logical queuing. Indeed, a possible implementation is to put the content of the whole data packet in different queues but however, another implementation is that the data packets are associated to e.g. an identification number and that the content of the data packets are physically not sorted at all but stored all together in one memory. The further processing is executed with the identification numbers until a data packet associated to a particular identification number is allowed to leave the buffer means.
Another way to reflect the result of the shared reserved bandwidth and the shared unreserved bandwidth is to generate according to a received data packet of a particular data flow an acceptance command or a discard command. This can be realized with an intelligent buffer being included in a communication network in order to share available bandwidth on a common link among a plurality of data flows that are transmitted via the common link. The intelligent buffer includes decision means in order to decide whether to accept or to discard an incoming data packet of one of the data flows. When the incoming data packet is accepted, it is stored in a buffer means, e.g., a first in first out buffer in order to be transmitted later on at the common link. The intelligent buffer further includes the processor according to the invention that is coupled to the decision means. The shared bandwidth signal of the processor is provided to the decision means in order to control the decision according to the shared bandwidth signal.
A third application of the present invention is a telecommunication system that includes at least one processor according to the present invention.